package study.datastructure.graph.prim;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-06 12:24
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 2024/6/6,
 */

//prim 实现最小生成树
public class PrimMST {
    Integer val;

    LinkedList<Edge>[] adjacencyList;

    public PrimMST(Integer val){
        this.val = val;
        adjacencyList=new LinkedList[val];
        for (int i = 0; i <val; i++) {
            adjacencyList[i]=new LinkedList<>();
        }


    }

    public void addEdge(int src,int dest,int weight){
        Edge edge=new Edge(src,dest,weight);
        Edge deverseEdge=new Edge(dest,src,weight);
        adjacencyList[src].add(edge);
        adjacencyList[dest].add(deverseEdge); //for undirected graph

    }

    public void primMST(){
        boolean[] inMST=new boolean[val];
        PriorityQueue<Edge> pq=new PriorityQueue<>();

        //从任意顶点开始 默认0开始
        int startVertex=0;
        inMST[startVertex]=true;

        for (Edge edge : adjacencyList[startVertex]) {
            pq.add(edge);
        }

        List<Edge> result=new ArrayList<>();
        while (!pq.isEmpty()){
            Edge edge = pq.poll();

            if (inMST[edge.src]&&inMST[edge.dest]){
                continue;
            }

            result.add(edge);
            int newVertex=inMST[edge.src]?edge.dest:edge.src;
            inMST[newVertex]=true;

            for (Edge newEdges : adjacencyList[newVertex]) {
                if (!inMST[newEdges.dest]){
                    pq.add(newEdges);
                }

            }
        }
        // 打印最小生成树
        System.out.println("Edges in the Minimum Spanning Tree:");
        for (Edge e : result) {
            System.out.println(e.src + " - " + e.dest + " : " + e.weight);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        PrimMST graph = new PrimMST(V);

        // 添加图中的边
        graph.addEdge(0, 1, 2);
        graph.addEdge(0, 3, 6);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 8);
        graph.addEdge(1, 4, 5);
        graph.addEdge(2, 4, 7);
        graph.addEdge(3, 4, 9);

        // 运行 Prim 算法并打印最小生成树
        graph.primMST();
    }

}
